import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InorderTraversal {
        public List<Integer> inorderRecursive(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            traverse(root, result);
            return result;
        }
        private void traverse(TreeNode node, List<Integer> result) {
            if (node == null) return;
            traverse(node.left, result);
            result.add(node.val);as
            traverse(node.right, result);
        }
    }


    public class InorderTraversal {
        public List<Integer> inorderIterative(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                curr = stack.pop();
                result.add(curr.val);
                curr = curr.right;
            }
            return result;
        }
    }

    public class Main {
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            InorderTraversal solution = new InorderTraversal();
            System.out.println("递归中序遍历结果: " + solution.inorderRecursive(root));
            System.out.println("非递归中序遍历结果: " + solution.inorderIterative(root));
        }
    }